<?php
/**
 * 二分查找
 *  二分的含义是每次能够缩小到原有规模的 1/2
 * User: yuesir
 * @author //github.com/yuesir
 */

/**
 *
 * @param array $bucket 要搜素的数组
 * @param mixed $target 要搜索的目标值
 * @return int 索引, 如果没有找到返回 -1
 */
function binarySearch(array $bucket, $target) {
    $index      = -1;
    $lowIndex   = 0;
    $highIndex  = count($bucket);

    while ($highIndex >= $lowIndex) {

        $midIndex   = floor($lowIndex + $highIndex);
        $midValue   = $bucket[$midIndex];

        if ($midValue == $target) {
            $index = $midIndex;
        } elseif ($midValue > $target) {
            $lowIndex = $midIndex + 1;
        } else {
            $highIndex = $midIndex - 1;
        }

    }

    return $index;
}